package top.humbleyuan.double_pointer;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 18:42
 * @Des 寻找重复数
 */
public class LeetCode_287 {
    // 佛洛依德双指针
    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};

        /**
         * 1. 找到相交点；
         * 2. 两个指针从头和从相交点同时出发，相遇时即环的起点(推导)
         * x = n * l + y
         * (x : 头到环的起点  n * l : n个环的长度  y : 相交点继续往前到环起点的距离)
         */

        // 先找相交点
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);

        // 找起点
        int head = 0;
        while(head != slow) {
            head = nums[head];
            slow = nums[slow];
        }

        System.out.println(slow);
    }
}
